package lc.q250_300;

import java.util.Arrays;

/**
 * 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
 *
 * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
 *
 * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
 * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
 * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
 * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
 * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
 *
 * 给定当前 board 的状态，更新 board 到下一个状态。
 *
 * 注意 你不需要返回任何东西。
 */
public class Q289 {

    public static void main(String[] args) {
        Q289 q289 = new Q289();
        int[][] board = new int[][]{
                new int[]{0,1,0},
                new int[]{0,0,1},
                new int[]{1,1,1},
                new int[]{0,0,0},
        };
        q289.gameOfLife2(board);
        for (int[] ints : board) {
            System.out.println(Arrays.toString(ints));
        }
//        System.out.println(q289.gameOfLife());
    }
    public void gameOfLife2(int[][] board) {
        // 不用复制。直接原地记录当前的状态和之后的状态
        // 因为每个board只有0和1，将其变成0,1,2,3就能记录两个状态了，高位是下一位状态，低位是当前状态
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                // 计算周围的八个格子活细胞个数
                int liveNeighbors = 0;
                // row-1 col-1一直到row+1 col+1
                for (int i = Integer.max(0, row - 1); i <= Integer.min(row + 1, board.length - 1); i++) {
                    for (int j = Integer.max(0, col - 1); j <= Integer.min(col + 1, board[0].length - 1); j++) {
                        // 防止越界
                        // 不算自己
                        if (!(j==col && i == row)) {
                            boolean live = (board[i][j] % 2) == 1;
                            if (live) {
                                liveNeighbors++;
                            }
                        }
                    }
                }
                // 按照规则
                if ((board[row][col] % 2) == 1) {
                    // 是活细胞。则按规则周围活细胞少于2个或者大于3个则死亡
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        // 算高位
                        board[row][col] = 1;
                    } else {
                        board[row][col] = 3;
                    }
                } else {
                    // 是死细胞，周围有三个以上就是活
                    if (liveNeighbors == 3) {
                        board[row][col] = 2;
                    } else {
                        board[row][col] = 0;
                    }
                }
            }
        }
        // 重新遍历还原状态
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                board[row][col] = board[row][col] / 2;
            }
        }
    }

    public void gameOfLife(int[][] board) {
        // 复制一个相同的board
        int[][] copyBoard = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            System.arraycopy(board[i], 0, copyBoard[i], 0, board[i].length);
        }
        // 重新遍历board
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                // 计算周围的八个格子活细胞个数
                int liveNeighbors = 0;
                // row-1 col-1一直到row+1 col+1
                for (int i = Integer.max(0, row - 1); i <= Integer.min(row + 1, board.length - 1); i++) {
                    for (int j = Integer.max(0, col - 1); j <= Integer.min(col + 1, board[0].length - 1); j++) {
                        // 防止越界
                        // 不算自己
                        if (!(j==col && i == row)) {
                            boolean live = copyBoard[i][j] == 1;
                            if (live) {
                                liveNeighbors++;
                            }
                        }
                    }
                }
                // 按照规则
                if (copyBoard[row][col] == 1) {
                    // 是活细胞。则按规则周围活细胞少于2个或者大于3个则死亡
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[row][col] = 0;
                    }
                } else {
                    // 是死细胞，周围有三个以上就是活
                    if (liveNeighbors == 3) {
                        board[row][col] = 1;
                    }
                }
            }
        }
    }
}
